//
// Created by francklinson on 2021/12/31 AT 14:47.
//
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * 用vector
     * @param n
     * @param edges
     * @param start
     * @param end
     * @return
     */
    bool validPath(int n, vector<vector<int>> &edges, int start, int end) {
        if (start == end)
            return true;
        // 建图
        vector<vector<bool>> graph(n, vector<bool>(n, false));
        for (auto &edge : edges) {
            graph[edge[0]][edge[1]] = true;
            graph[edge[1]][edge[0]] = true;
        }
        // bfs
        unordered_set<int> seen;
        queue<int> q;
        q.push(start);
        seen.insert(start);
        while (!q.empty()) {
            int p = q.front();
            q.pop();
            for (int i = 0; i < n; ++i) {
                if (graph[p][i]) {
                    if (i == end)
                        return true;
                    if (!seen.count(i)) {
                        seen.insert(i);
                        q.push(i);
                    }
                }
            }
        }
        return false;
    }

    /**
     * 用hash
     * @param n
     * @param edges
     * @param start
     * @param end
     * @return
     */
    bool validPath2(int n, vector<vector<int>> &edges, int start, int end) {
        if (start == end)
            return true;
        // 建图
        unordered_map<int, unordered_set<int>> graph;
        for (auto &edge : edges) {
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }
        // bfs
        unordered_set<int> seen;
        queue<int> q;
        q.push(start);
        seen.insert(start);
        while (!q.empty()) {
            int p = q.front();
            q.pop();
            for (const int &x:graph[p]) {
                if (x == end)
                    return true;
                if (!seen.count(x)) {
                    seen.insert(x);
                    q.push(x);
                }

            }
        }
        return false;
    }

};

int main() {
    Solution solution;
    vector<vector<int>> edges{{0, 1},
                              {1, 2},
                              {2, 0}};
    cout << solution.validPath(3, edges, 0, 2) << endl;
    cout << solution.validPath2(3, edges, 0, 2) << endl;
    return 0;
}

